1. Field of the Invention
The present invention is directed to digital logic design systems. More particularly, the invention is directed. to automated digital logic synthesis and placement systems.
2. Background of the Related Art
Prior art computer aided design (CAD) systems for the design of integrated circuits and the like assist in the design thereof by providing a user with a set of software tools running on a digital computer. In the prior art, the process of designing an integrated circuit on a typical CAD system was done in several discrete steps using different software tools.
First, a schematic diagram of the integrated circuit is entered interactively to produce a digital representation of the integrated circuit elements and their interconnections. This representation may initially be in a hardware description language such as Verilog and then translated into a register transfer level (RTL) description in terms of pre-designed functional blocks, such as memories and registers. This may take the form of a data structure called a net list.
Next, a logic compiler receives the net list and, using a component database, puts all of the information necessary for layout, verification and simulation into object files whose formats are optimized specifically for those functions.
Afterwards, a logic verifier checks the schematic for design errors, such as multiple outputs connected together, overloaded signal paths, etc., and generates error indications if any such design problems exist. In many cases, the IC designer improperly connected or improperly placed a physical item within one or more cells. In this case, these errors are flagged to the IC designer so that the layout cells may be fixed so that the layout cells perform their proper logical operation. Also, the verification process checks the hand-laid-out cells to determine if a plurality of design rules have been observed. Design rules are provided to integrated circuit designers to ensure that a part can be manufactured with greater yield. Most design rules include hundreds of parameters and, for example, include pitch between metal lines, spacing between diffusion regions in the substrate, sizes of conductive regions to ensure proper contacting without electrical short circuiting, minimum widths of conductive regions, pad sizes, and the like. If a design rules violation is identified, this violation is flagged to the IC designer so that the IC designer can properly correct the cells so that the cells are in accordance with the design rules.
Then, using a simulator the user of the CAD system prepares a list of vectors representing real input values to be applied to the simulation model of the integrated circuit. This representation is translated into a form which is best suited to simulation. This representation of the integrated circuit is then operated upon by the simulator which produces numerical outputs analogous to the response of a real circuit with the same inputs applied. By viewing the simulation results, the user may then determine if the represented circuit will perform correctly when it is constructed. If not, he or she may re-edit the schematic of the integrated circuit, re-compile and re-simulate. This process is performed iteratively until the user is satisfied that the design of the integrated circuit is correct.
Then, the human IC designer presents as input to a logic synthesis tool a cell library and a behavioral model. The behavioral circuit model is typically a file in memory which looks very similar to a computer program. The behavioral circuit model contains instructions which define logically the operation of the integrated circuit. The logic synthesis tool receives as input the instructions from the behavioral circuit model and the library cells from the library. The synthesis tool maps the instructions from the behavioral circuit model to one or more logic cells from the library to transform the behavioral circuit model to a gate schematic net list of interconnected cells. A gate schematic net list is a data base having interconnected logic cells which perform a logical function in accordance with the behavioral circuit model instructions. Once the gate schematic net list is formed, it is provided to a place and route tool.
The place and route tool is used to access the gate schematic net list and the library cells to position the cells of the gate schematic net list in a two-dimensional format within a surface area of an integrated circuit die perimeter. The output of the place and route step is a two-dimensional physical design file which indicates the layout interconnection and two-dimensional IC physical arrangements of all gates/cells within the gate schematic net list.
Interconnect delay is a major concern in deep sub-micron technologies for two reasons: as the technologies scale, the feature sizes are shrinking. The gate resistance and capacitance scales better with this shrinking than the interconnect resistance and capacitance. Moreover, although the local interconnect lengths are shrinking, lengths of global interconnect and long wires are increasing as chip sizes increase. As the interconnect delay is proportional to the square of the wire length, this has a significant impact on the over-all timing of the chip. Buffer insertion and wire sizing are the two main tools to manage interconnect delay. Among these, buffer insertion offers the possibility of reducing cross talk hazards due to signal regeneration (apart from any cross talk reduction obtained by offsetting inverters).
In the deep sub-micron technologies, the contribution of interconnect delay can constitute as much as 80% of the total delay. Interconnect delay is proportional to the square of the wire length. As a result, long wires are a major concern in designing high performance chips since the long wire lengths increase quadratically with technology scaling. Buffer insertion and wire sizing are the two main tools to manage interconnect delay.
Apart from the wire length, the interconnect delay is a function of various technology parameters, net topology, source and sink parameters etc. The exact formulation of the interconnect delay and an optimal buffering scheme to minimize it can be very complex. Since many of these parameters are dependent on specific net instances, a complex analysis/buffering strategy would have limited practical use when buffering a design with tens of thousands of long wires.
The present invention has been made with the above problems of the prior art in mind, and a first object of the present invention is to provide a wire delay model which allows accurate prediction of wire delays in the presence of long wires. The delay estimates account for the effect of buffering on the delay. The model is exact under some assumptions and is a good heuristic approximation for more general cases.
It is a further object of the present invention to provide a method which derives the optimal buffering distance and the optimal buffer size in long wires under some assumptions. These formulae are also good heuristic approximations for more general cases.
It is another object of the present invention to provide a method using delay models which allows placement algorithms to account for the effect of buffering of long wires on delay and capacitance without actually inserting buffers in the design.
It is a still further object of the present invention to provide a method in which design independence of the optimal buffering distance and the optimal buffer size can be used to efficiently buffer long wires. This strategy can also be applied in a placement-optimization flow to implement the delays and capacitances estimated by the proposed delay model during placement.
It is a still further object of the present invention to provide a delay model in which the wire delay is a function of the wire length and wire width and spacing. This formulation can be used to trade-off length versus wire width and/or wire spacing to achieve a target delay.
It is yet another object of the present invention to provide a delay model that can be used to estimate wire delays at any stages in a placement-optimization flow. This delay can then be held constant throughout the rest of the flow by varying wire width and spacing as the wire length changes.
It is a still further object of the present invention to provide a delay model that can be used to implement a desired wire delay by wire width, spacing or length changes to meet a target stage delay (delay of driving gate+wire delay). Given a fixed placement, this can be used to balance fast/slow gate delays in the circuit. This can increase the flexibility of gate sizing algorithms.
It is yet another object of the present invention to provide an algorithm which selects target wire delays in a design. The algorithm can be applied in conjunction with a gate sizing/gate delay selection algorithm to trade-off gate and wire delays and the associated area/routing congestion. These target delays are then met by varying the wire widths and spacing. If no combination of wire delays can satisfy the timing constraints, the circuit cannot meet timing for the given selection of gate sizes. This can be used as a timing checkpoint in a placement flow.
It is another object of the present invention to provide a buffering algorithm which combines optimal buffering distance results with previous works on buffer insertion using dynamic programming.
It is another object of the present invention to provide a method in which constant wire delay placement-optimization flow uses the above results and algorithms to hold wire delay constant.
It is another object of the present invention to provide a technique in which the delay of an optimally buffered wire can be modeled using just library RC parameters for any given wire size and spacing.
It is a still further object of the present invention to provide such a technique in which very large circuit designs can be buffered and sized/spaced efficiently and which allows modeling the effect of buffering without actually inserting buffers in the design.
It is a further object of the present invention to provide a technique in which an increase in wire delay can be made linear in length, as opposed to quadratic for an unoptimized wire, via buffering.
It is yet another object of the present invention to provide a technique in which an increase in wire delay can be made independent of its length, as opposed to the quadratic dependency of an unoptimized wire, via buffering and wire sizing/spacing.
The above objects are achieved according to an aspect of the present invention by providing a strategy for optimal buffering in the case of a long wire buffered with an arbitrary number of equally spaced single-size buffers. A simple but efficient technique is proposed using this to choose a buffer size and determine a good inter-buffering distance up front, thus enabling fast, efficient buffer insertion. The analysis also allows representing delays of long wires as a simple function of the length and buffer and wire widths. Based on this, a novel constant wire delay approach is proposed where the proposed wire delay model is used for fairly accurate prediction of wire delays early in the design process and these predictions are later met via buffer insertion and wire sizing.
The present invention provides a buffering strategy that is optimal in the case of an infinitely long wire buffered with an arbitrary number of equally spaced single-size buffers. In practice, this technique can be used to choose a buffer size and determine a good inter-buffering distance up front, thus enabling fast, efficient buffer insertion.
The delay due to long wires can be represented as a linear function of the length. Based on this, a novel constant wire delay approach can be developed where the proposed wire delay model is used for fairly accurate prediction of wire delays early in the design process and these predictions are later met via buffer insertion and wire sizing.
The present invention initially treats the above problem in the case of an infinitely long wire buffered with an arbitrary number of equally spaced single-size buffers. A simple but efficient technique is proposed using this to choose a buffer size and determine a good inter-buffering distance up front, thus enabling fast, efficient buffer insertion. The analysis presented here also allows representing delays of long wires as a simple function of the length and buffer and wire widths. Based on this, a novel constant wire delay approach is proposed where the proposed wire delay model is used for fairly accurate prediction of wire delays early in the design process and these predictions are later met via buffer insertion and wire sizing.